iT邦幫忙

2021 iThome 鐵人賽

DAY 22
0
自我挑戰組

當你凝視linux, linux也在凝視你系列 第 22

Day22 跟著 spinlock 旋轉吧

  • 分享至 

  • xImage
  •  

前言

昨天講完了最基礎的 atomic的資訊,瞭解了 atomic可以保護某個變數的資料正確性,當有多個行程或是執行序想要同時存取對某個變數,利用atomic可以順利地達成目的,但是當有些操作是要對作業系統內部的資料結構進行操作時,只有使用atomic對某個資料進行保護是不夠的,這個時候就需要其他的武器來應付這樣的狀況,像是今天要談的spinlock。

spinlock(自旋鎖)

spinlock是Linux裡面最常見的鎖機制,在同一個時刻,spinlock只能被一個行程持有,如果有另一個行程想要獲取已經被持有的spinlock,那麼想獲取的行程就會一直忙碌等待,直到所得持有者釋放該鎖。自旋鎖有幾個性質。

  1. 想獲取鎖的行程會一直忙碌直到持有鎖的行程釋放鎖
  2. 應該只用在比較短的 C.S (critical section),若是C.S較長,則浪費許多在等待的時間
  3. 持有鎖的行程不能進入睡眠
  4. 在C.S區內必須要關閉中斷

<include/linux/spinlock_types.h>

typedef struct raw_spinlock {
	arch_spinlock_t raw_lock;
} raw_spinlock_t;

typedef struct spinlock {
	union {
		struct raw_spinlock rlock;

#ifdef CONFIG_DEBUG_LOCK_ALLOC
# define LOCK_PADSIZE (offsetof(struct raw_spinlock, dep_map))
		struct {
			u8 __padding[LOCK_PADSIZE];
			struct lockdep_map dep_map;
		};
#endif
	};
} spinlock_t;

Linux 內,spinlock的修改大概可以分成三個階段。

  • spinlock
  • Ticket spinlock
  • Queued Spinlock
  1. spinlock
    在Linux2.6.25之前,spinlock的資料結構就只是一個簡單的unsigned 變數,但是在這樣簡潔的狀態之下,會發生很多其他的問題,特別是當很多個CPU同時要取得同一個spinlock的時候,可能會導致嚴重的不公平及性能下降,剛釋放鎖的CPU很有可能馬上再次獲得該所的使用權;或是與資料同一個NUMA節點的CPU有可能搶先獲得鎖,而沒有考慮已經在所外面等待很久的CPU。也因此Linux 2.6.25之後,出現了基於排隊的FIFO自旋鎖機制。

  2. Ticket spinlock
    Ticket spinlock大概就像是抽號碼牌排隊,想獲取鎖的行程,會得到兩個數字,一個是目前的號碼,與自己的號碼,當自己的號碼是下一個號碼的時候,才會換成該行程獲取鎖。以下是部份程式碼

static inline void arch_spin_unlock(arch_spinlock_t *lock)
{
    lock->tickets.owner++;
}

static inline void arch_spin_lock(arch_spinlock_t *lock)
{
    [LL/SC]

    while (lockval.tickets.next != lockval.tickets.owner) {
        wfe();
        lockval.tickets.owner = READ_ONCE(lock->tickets.owner);
    }
}

由上面的程式碼可以發現,如果有多個CPU同時想獲取同一個鎖時,有可能會造成CPU cacheline bouncing,也就是多個CPU上的快取同時失效的狀態,這個問題出現在上述程式碼12行,因為每次都要拿取 lock->tickets.owner的值,如果值沒有改變,就只要拿取cache的資料就可以了,當一個行程完成工作, lock->tickets.owner的值改變的時候,所有爭搶鎖的CPU上的cache 會同時被invalidate,所有CPU要重新從記憶體上拿取最新的資料,這樣是極度浪費效能的。

  1. 基於MCS算法的 Quened spinlock
    在 ticket spinlock中,因為唯一一個能拿到鎖的是下一個行程,但是因為 lock->tickets.owner的改變所有的cpu都要更新cacheline,造成極大的效能浪費,因此基於MCS的quened spinlock因應而生。
    這部分有些複雜,目前我還沒有看懂,待以後整理
    MCS lock
    queued spinlock

Linux 核心設計: 多核處理器和 spinlock


上一篇
Day21 atomic, memory barrier
下一篇
Day23 semaphore, mutex
系列文
當你凝視linux, linux也在凝視你30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言